(1) Field of the Invention
The present invention relates to a compiler that converts a source program written in high-level language such as the C++ language into an executable program written in machine language, and particularly to a compiler that converts said source program into an executable program that are executed on a computer having a cache memory.
(2) Description of the Related Art
A variety of compilers for computers having cache memory have been proposed so far. For example, there is a compiler that lays out a set of data items that are accessed at similar timings (e.g. a set of data items with overlapping lifetimes) in contiguous locations on the main memory (for example, see Japanese Laid-Open Patent application No. 7-129410). By laying out, in consecutive locations on the main memory, a set of data items that are accessed at similar timings, these data items are laid out on the same block on the cache memory at one time. Accordingly, it becomes possible to increase the hit rate of the cache memory.
However, if addresses on the main memory of the respective data items that are accessed at similar timings are determined in a way that enables such data items to be laid out on the same block, and if the total size of these data items is larger than the size of such block, it is impossible to write all data included in such data items to the same block at one time. This causes a cache conflict on the same block between or among data included in the same data items, resulting in frequent cache misses. This problem is especially notable in cache memories using a direct mapping scheme in which only one block is associated with one set.